package thired.class11_digui;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.List;

//全排列
public class Class03_PrintAllPermutations {
    public static List<String> permutation1(String s){
        ArrayList<String> res = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return res;
        }
        char[] str = s.toCharArray();
        ArrayList<Character> rest = new ArrayList<Character>();
        for (char cha : str) {
            rest.add(cha);
        }
        String path = "";
        f(rest, path, res);
        return res;
    }
    public static void f(ArrayList<Character> rest,String path, ArrayList<String> res){
        if(rest.isEmpty()){
            res.add(path);
            return;
        }else{
            for (int i = 0; i < rest.size(); i++) {
                char cur = rest.get(i);
                rest.remove(i);
                f(rest,path + cur,res);
                rest.add(i,cur);
            }
        }
    }


    public static List<String> permutation2(String s){
        ArrayList<String> res = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return res;
        }
        char[] str = s.toCharArray();
        ArrayList<Character> rest = new ArrayList<Character>();
        for (char cha : str) {
            rest.add(cha);
        }
        String path = "";
        g(str,0,res);
        return res;
    }
    public static void g(char[] str,int index,ArrayList<String> res){
        if(index == str.length){
            res.add(String.valueOf(str));
            return;
        }else{
            for (int i = index; i < str.length; i++) {
               swap(str,i,index);
               g(str,index + 1,res);
               swap(str,i,index);
            }
        }
    }

    public static List<String> permutation3(String s){
        ArrayList<String> res = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return res;
        }
        char[] str = s.toCharArray();
        ArrayList<Character> rest = new ArrayList<Character>();
        for (char cha : str) {
            rest.add(cha);
        }
        g1(str,0,res);
        return res;
    }
    public static void g1(char[] str,int index,ArrayList<String> res){
        if(index == str.length){
            res.add(String.valueOf(str));
            return;
        }else{
            boolean[] visited = new boolean[256];
            for (int i = index; i < str.length; i++) {
                if (!visited[str[i]]) {
                    visited[str[i]] = true;
                    swap(str, index, i);
                    g1(str, index + 1, res);
                    swap(str, index, i);
                }
            }
        }
    }



    public static void swap(char[] chs, int i, int j) {
        char tmp = chs[i];
        chs[i] = chs[j];
        chs[j] = tmp;
    }

    public static void main(String[] args) {
        String s = "acc";
        List<String> ans1 = permutation1(s);
        for (String str : ans1) {
            System.out.println(str);
        }
        System.out.println("=======");
        List<String> ans2 = permutation2(s);
        for (String str : ans2) {
            System.out.println(str);
        }
        System.out.println("=======");
        List<String> ans3 = permutation3(s);
        for (String str : ans3) {
            System.out.println(str);
        }

    }
}
